/**
 * 项目名称: Topic_953.cpp
 * 项目路径: study/DataStructure/刷题/一轮/第六天 数组+散列表
 * 编辑时间: 2024年09月07日09时41分24秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    struct Node {
        int val;
        int level;
    };
    const int N = 200003;
    const int null = 0x3f3f3f3f;
    Node h[200003];

    int find(int x) {
        int k = (x % N + N) % N;
        while (h[k].val != null && h[k].val != x) {
            k++;
            if (k == N)k = 0;
        }
        return k;
    }

    bool isAlienSorted(vector<string> &words, string order) {
        for (int i = 0; i < N; i++)h[i].val = null;

        for (int i = 0; i < order.length(); i++) {
            int k = order[i] - 'a';
            h[find(k)].val = k;
            h[find(k)].level = i;
        }

        for (int i = 0; i < words.size() - 1; i++) {
            string p_1 = words[i];
            string p_2 = words[i + 1];

            int len = max(p_1.size(), p_2.size());
            for (int j = 0; j < len; j++) {
                if (j + 1 > p_1.size())break;
                if (j + 1 > p_2.size())return false;
                int v_1 = p_1[j] - 'a';
                int v_2 = p_2[j] - 'a';

                int add_1 = h[find(v_1)].level;
                int add_2 = h[find(v_2)].level;

                if (add_1 > add_2)return false;
                if (add_1 < add_2)break;
            }
        }
        return true;
    }
};
